package com.shihb.chapter02function

import java.text.SimpleDateFormat
import java.util.Date

/**
 * Description:递归高级
 *
 * @author shihb
 * @date 2020/10/2 13:03
 */
object Demo09RecursionPlus {
  /**
   * 练习一，计算1-99999999L的和
   * 得出结论递归调用和普通调用速度影响不大
   */
  def exercise1: Unit ={
    val sdf:SimpleDateFormat = new SimpleDateFormat("yyyyMMdd HH:mm:ss")
    var res=BigInt(0)
    var num=BigInt(1)
    var maxVal=BigInt(99999999L)
    val start:Date=new Date()
    // 传统的方式
    while(num<=maxVal){
      res+=num
      num+=1
    }
    val end:Date=new Date()
    println("传统方式")
    println(sdf.format(start),sdf.format(end))
    val start1:Date=new Date()
    // 递归方式
    mx(1,0)
    val end1:Date=new Date()
    println("递归方式")
    println(sdf.format(start1),sdf.format(end1))

  }
  // 递归求和
  def mx(num:BigInt,sum:BigInt):BigInt={
    if(num<=99999999L) mx(num+1,sum+num) else sum
  }

  /**
   * 练习二：求最大值和翻转字符串
   * 体现递归的有雅兴
   */
  def exercise2: Unit ={
    println(myMax(List(943)))
    println(myMax(List(943, 370, 361, 4, 302734, 483)))
    println(reverseString("uoy evol i"))
  }
  // 递归求最大值
  def myMax(list: List[Int]): Int ={
    // 递归告诉计算机做什么,而不是告诉计算机怎么做(迭代)
    if(list.isEmpty){
      throw  new NoSuchElementException
    }else if(list.size==1){
      list.head
    }else if(list.head>myMax(list.tail)){
      list.head
    }else{
      myMax(list.tail)
    }
  }
  def reverseString(s:String):String={
    if (s.length==1) s else reverseString(s.tail)+s.head
  }


  /**
   * 递归陷阱：避免重复计算
   */
  def exercise3={
    var count=BigInt(0)
    println(fbn(21))
    println("调用了count="+count)

    //实现斐波那契数,调用次数会指数增长调用
    def fbn(index: Int): Int = {
      count+=1
      //
      if (index == 2 || index == 1) 1 else fbn(index - 1) + fbn(index - 2)
    }
  }

  def main(args: Array[String]): Unit = {

//    exercise1
    exercise3
  }

}
